package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202409;

public class leetcode20240920 {
    /**
     * 统计特殊整数：每一个数位各不相同
     * @param n
     * @return
     */
    public int countSpecialNumbers(int n) {
        int ans=0;
        boolean[] visited=new boolean[10];
        // 回溯算法，第一个数字只能是1~9
        for(int i=1;i<=9;i++){
            visited[i]=true;
            ans+=dfs(n,i,visited);
            visited[i]=false;
        }
        return ans;
    }

    private int dfs(int n,long num,boolean[] visited){
        if(num>n){
            return 0;
        }
        int ans=0;
        for(int i=0;i<=9;i++){
            if(visited[i]) continue;
            visited[i]=true;
            ans+=dfs(n,num*10+i,visited);
            visited[i]=false;
        }
        return ans+1;
    }

}
